package a07_二叉树;

import java.util.LinkedList;

/**
 * <p>
 * a17_路径总和复习3
 * </p>
 *
 * @author flyduck
 * @since 2025/4/11
 */
public class a17_路径总和复习3 {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null && targetSum == 0){
            return false;
        }
        LinkedList<Integer> path = new LinkedList<>();
        return traversal(path, root, 0, targetSum);
    }

    public static final String[] dirs = new String[]{"left","right"};

    private boolean traversal(LinkedList<Integer> path,
                           TreeNode node,
                           int sum,
                           int targetSum){
        if (node != null) {
            if(node.left == null && node.right == null){
                path.add(node.val);
                sum += node.val;
                if(sum == targetSum){
                    return true;
                }else {
                    path.removeLast();
                    sum -= node.val;
                    return false;
                }
            }
        }else {
            return false;
        }

        for (String dir : dirs) {
            path.add(node.val);
            sum += node.val;
            if("left".equals(dir)){
                boolean traversal = traversal(path, node.left, sum, targetSum);
                if (traversal) {
                    return true;
                }
            }else {
                boolean traversal = traversal(path, node.right, sum, targetSum);
                if (traversal) {
                    return true;
                }
            }
            sum -= node.val;
            path.removeLast();
        }

        return false;
    }
}
